﻿/*
题目: 出界的路径数

给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。

给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。

https://leetcode.cn/problems/out-of-boundary-paths/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution{
public:
    int dirs[5] = {0, -1, 0, 1, 0};
    const int MOD = (int)1e9 + 7;

    int findPaths(int n, int m, int maxMove, int startRow, int startColumn) {
        // cache[x][y][k] 表示坐标在 (x, y) 步数为 k 时的出界数量
        vector<vector<vector<int>>> cache(n, vector<vector<int>>(m, vector<int>(maxMove + 1, -1)));
        int res = 0;

        auto ok = [n, m](int x, int y) { return x >= 0 && x < n&& y >= 0 && y < m; };

        cache[startRow][startColumn][0] = 0;
        function<int(int, int, int)> dfs =
            [&](int x, int y, int k) {
                if (k == -1) {       // 已经没步骤走了
                    return 0;
                }
                if (ok(x, y) && cache[x][y][k] != -1) {     // 走记忆化
                    return cache[x][y][k];
                }
                if (!ok(x, y)) {                // 如果出界了
                    return 1;
                }

                int sum = 0;
                for (int i = 0; i < 4; i++) {
                    int nx = x + dirs[i];
                    int ny = y + dirs[i + 1];

                    sum = ((long long)sum + dfs(nx, ny, k - 1)) % MOD;
                }

                return cache[x][y][k] = sum;
            };

        dfs(startRow, startColumn, maxMove);
        return cache[startRow][startColumn][maxMove];
    }
};